/*
 * @lc app=leetcode.cn id=106 lang=cpp
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int>& inorder,int inStart,int inEnd,
                    vector<int>& postorder,int postStart,int postEnd)
                    {
                        if(inStart > inEnd)
                        {
                            return NULL;
                        }

                        int rootVal = postorder[postEnd];
                        int index = -1;
                        int leftsize = 0;
                        for(int i = inStart ; i <= inEnd ; i++)
                        {
                            if(inorder[i] == rootVal)
                            {
                                index = i;
                                leftsize = i - inStart;
                            }
                        }         
                        
                        TreeNode * root = new TreeNode(rootVal);

                        root->left = build(inorder , inStart , index - 1 , postorder , postStart , postStart + leftsize - 1);
                        root->right = build(inorder , index + 1 , inEnd , postorder , postStart + leftsize , postEnd - 1 );

                        return root;
                    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        //后序的尾结点决定头结点的位置，中序决定左右子节点
        return build(inorder , 0 , inorder.size() - 1 , postorder , 0 , postorder.size() -1 );
    }
};
// @lc code=end

